﻿#define _CRT_SECURE_NO_WARNINGS  1
#include<vector>
#include<string>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

//209.长度最⼩的⼦数组
class Solution1 {
public:
    int minSubArrayLen(int target, vector<int>& nums)
    {
        int n = nums.size();
        int sum = 0;
        int len = INT_MAX;
        for (int left = 0, right = 0; right < n; right++)
        {
            sum += nums[right];
            while (sum >= target)          //后面的一定大于target，但是len会变长，所以是无效计算
            {
                len = min(len, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }

        return len == INT_MAX ? 0 : len;
    }
};


//3.⽆重复字符的最⻓⼦串
class Solution2 {
public:
    int lengthOfLongestSubstring(string s)
    {
        int n = s.size();
        int len = 0;
        int ret = 0;
        char check[256] = { 0 };
        for (int left = 0, right = 0; right < n;right++)
        {
            check[s[right]]++;
            while (check[s[right]] > 1)
            {
                check[s[left]]--;
                left++;
             }
            ret = max(ret, right - left + 1);

        }

        return ret;
    }
};


//1004.最⼤连续1的个数III
class Solution3
{
public:
    int longestOnes(vector<int>& nums, int k)
    {
        //求一个最长子数组，该子数组最多有K个0.
        int n = nums.size();
        int len = 0;
        int curk = 0;
        for (int left = 0, right = 0; right < n; right++)
        {
            if (nums[right] == 0) ++curk;
            while (curk > k)
            {
                if (nums[left] == 0)
                {
                    curk--;
                }
                left++;
            }
            len = max(len, right - left + 1);
        }
        return len;
    }
};


//1658.将x减小到0的最⼩操作数
class Solution4
{
public:
    int minOperations(vector<int>& nums, int x)
    {
        int n = nums.size();
        int sum = 0;
        for (auto ch : nums)
        {
            sum += ch;
        }
        int target = sum - x;   //找减去sum-x的最长数组
        if (target < 0) return -1;    //x比sum还大，此数不存在
        int ret = -1;

        int now = 0;
        for (int left = 0, right = 0; right < n; right++)
        {

            now += nums[right];
            while (now > target)
            {
                now -= nums[left];
                left++;
            }
            if (now == target)   //找到一组，更新长度
            {
                ret = max(ret, right - left + 1);
            }
        }

        if (ret == -1) return ret;
        else return n - ret;
    }
};


//904.⽔果成篮
class Solution5 {
public:
    int totalFruit(vector<int>& fruits)
    {
        int n = fruits.size();
        int ret = 0;
        int* count = new int[n]();
        int flag = 0;
        for (int left = 0, right = 0; right < n; right++)
        {
            if (count[fruits[right]] == 0)
            {
                flag++;
            }
            count[fruits[right]]++;

            while (flag > 2)
            {
                count[fruits[left]]--;
                if (count[fruits[left]] == 0)
                    flag--;
                left++;
            }


            ret = max(ret, right - left + 1);

        }

        delete[] count;
        return ret;
    }
};


//438.找到字符串中所有字⺟异位词
class Solution6 {
public:
    vector<int> findAnagrams(string s, string p)
    {
        int* count = new int[256]();
        for (auto ch : p)
        {
            count[ch]++;
        }
        int flag = 0;
        vector<int> ret;
        for (int left = 0, right = 0; right < s.size(); )
        {
            if (count[s[right]] > 0)
            {
                //存在这个数
                flag++;
                count[s[right]]--;
                right++;
            }
            else
            {
                while (p.find(s[left]) == -1)
                {
                    left++;
                }
                count[s[left]]++;
                flag = 0;
            }

            if (flag == p.size())
            {
                ret.push_back(left);
                flag = 0;
            }

        }

        return ret;
    }
};

//30.串联所有单词的⼦串
class Solution7 {
public:
    vector<int> findSubstring(string s, vector<string>& words)
    {
        int len = words[0].size();
        int m = words.size();
        unordered_map<string, int> hash1;
        vector<int>ret;
        for (auto& ch : words) hash1[ch]++;

        for (int i = 0; i < len; i++)
        {
            int count = 0;
            unordered_map<string, int>hash2;
            for (int left = i, right = i; right + len <= s.size(); right += len)
            {
                string str = s.substr(right, len);
                hash2[str]++;
                if (hash1.count(str) && hash2[str] <= hash1[str])count++;
                if (right - left + 1 > m * len)
                {
                    string out = s.substr(left, len);
                    if (hash1.count(out) && hash2[out] <= hash1[out])count--;
                    hash2[out]--;
                    left += len;
                }
                if (count == m)
                {
                    ret.push_back(left);
                }
            }
        }
        return ret;
    }
};

//76.最⼩覆盖⼦串
class Solution8 {
public:
    string minWindow(string s, string t)
    {
        int hash1[200] = { 0 };
        int kind = 0;
        for (auto ch : t)
        {
            if (hash1[ch] == 0)
                kind++;
            hash1[ch]++;
        }

        int hash2[200] = { 0 };
        int minlen = INT_MAX;
        int begin = -1;
        for (int left = 0, right = 0, count = 0; right < s.size(); right++)
        {
            hash2[s[right]]++;
            if (hash1[s[right]] == hash2[s[right]])count++;

            while (count == kind)
            {
                if (minlen > right - left + 1)
                {
                    minlen = right - left + 1;
                    begin = left;
                }
                if (hash1[s[left]] == hash2[s[left]]) count--;
                hash2[s[left]]--;
                left++;

            }
        }

        if (begin == -1) return "";
        else return s.substr(begin, minlen);
    }
};
int main()
{
    Solution1 s;
    vector<int> v{ 3,3,3,1,2,1,1,2,3,3,4 };

}